package com.hr.tuling.list;

/**
 * 查找单链表倒数第 k 个节点
 */
public class GetLastIndexOfNode {
    public static void main(String[] args) {
        // 1.创建一个单链表
        Node lastNode = new Node(55);
        Node node4 = new Node(44, lastNode);
        Node node3 = new Node(33, node4);
        Node node2 = new Node(22, node3);
        Node headNode = new Node(11, node2);
        // 2.查找单链表倒数第 k 个节点
        Node node = getLastIndexOfNode(headNode, 5);
        System.out.println(node.getData());
    }

    /**
     * 查找单链表倒数第 k 个节点
     *
     * @param headNode 单链表的首节点
     *                 37
     * @param k        表示单链表倒数第 k 个节点
     * @return 返回单链表中倒数第 k 个节点
     */
    public static Node getLastIndexOfNode(Node headNode, int k) {
        // 1.处理 headNode 为 null 的情况
        if (headNode == null) {
            throw new NullPointerException("headNode 为 null");
        }
        // 此处 k 的合法取值范围：[1, 单链表长度]
        // 2.定义 first 和 second 指针，并且设置它们的初始值为单链表的首节点
        Node first = headNode, second = headNode;
        // 3.通过循环，让 first 指针往后移动 k-1 次
        for (int i = 0; i < k - 1; i++) {
            first = first.getNext();
        }
        // 4.通过循环，每次让 first 和 second 往后移动一次。
        // 当 first 指向的节点为单链表的尾节点时，则停止移动
        while (first.getNext() != null) {
            // 5.设置 first 和 second 每次往后移动一次
            first = first.getNext();
            second = second.getNext();
        }
        // 6.返回单链表中倒数第 k 个节点
        return second;
    }
}